package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 16:37
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
root到叶子节点，中间的节点数目
最少的数目，就是最低深度
 */
public class a_最低深度 {
    public static void main(String[] args) {
        a_最低深度 test = new a_最低深度();
        b_MyBinaryTreebyLinked<Integer, Integer> Btree = new b_MyBinaryTreebyLinked<>();
        Btree.insert(1,null);
        Btree.insert(2,null);
        Btree.insert(3,null);
        Btree.insert(4,null);
        Btree.insert(5,null);
        Btree.insert(6,null);
        System.out.println(test.minDepth(Btree.getRoot()));
    }

    public int minDepth(BSTNode<Integer, Integer> node) {
        if (node == null) {//空节点，递归出口
            return 0;
        }
        int depLeft = minDepth(node.left);
        int depRight = minDepth(node.right);

        if (depLeft == 0 || depRight == 0) {//单支节点
            return 1 + depLeft + depRight;//depLeft + depRight,其中一个加数是0
        }
        return 1 + Math.min(depLeft, depRight);
    }
}
